Wireless communications systems are becoming increasingly important worldwide. Wireless cellular telecommunications systems are rapidly replacing conventional wire-based telecommunications systems in many applications. Commercial mobile radio service provider networks, and specialized mobile radio and mobile data radio networks are examples. The general principles of wireless cellular telephony have been described variously, for example in U.S. Pat. No. 5,295,180 to Vendetti, et al filed Apr. 8, 1992, which is incorporated herein by reference. There is great interest in using existing infrastructures for wireless communication systems for locating people and/or objects in a cost-effective manner. Such a capability would be invaluable in a variety of situations, especially in emergency or crime situations. Due to the substantial benefits of such a location system, several attempts have been made to design and implement such a system. Systems have been proposed that rely upon signal strength and trilateralization techniques to permit location include those disclosed in U.S. Pat. No. 4,818,998 filed Mar. 31, 1986 and U.S. Pat. No. 4,908,629 filed Dec. 5, 1988 both to Apsell et al. (“the Apsell patents”), and U.S. Pat. No. 4,891,650 to Sheffer (“the Sheffer patent”) filed May 16, 1988. The Apsell patents disclose a system employing a “homing-in” scheme using radio signal strength, wherein the scheme detects radio signal strength transmitted from an unknown location. This signal strength is detected by nearby tracking vehicles, such as police cruisers using receivers with directional antennas. Alternatively, the Sheffer patent discloses a system using the FM analog cellular network. This system includes a mobile transmitter located on a vehicle to be located. The transmitter transmits an alarm signal upon activation to detectors located at base stations of the cellular network. These detectors receive the transmitted signal and transmit, to a central station, data indicating the signal strength of the received signal and the identity of the base stations receiving the signal. This data is processed to determine the distance between the vehicle and each of the base stations and, through trilateralization, the vehicle's position. However, these systems have drawbacks that include high expense in that special purpose electronics are required. Furthermore, the systems are generally only effective in line-of-sight conditions, such as rural settings. Radio wave surface reflections, refractions and ground clutter cause significant distortion, in determining the location of a signal source in most geographical areas that are more than sparsely populated. Moreover, these drawbacks are particularly exacerbated in dense urban canyon (city) areas, where errors and/or conflicts in location measurements can result in substantial inaccuracies.
Another example of a location system using time of arrival and triangulation for location are satellite-based systems, such as the military and commercial versions of the Global Positioning Satellite system (GPS). GPS can provide accurate position determination (i.e., about 100 meters error for the commercial version of GPS) from a time-based signal received simultaneously from at least three satellites. A ground-based GPS receiver at or near the object to be located determines the difference between the time at which each satellite transmits a time signal and the time at which the signal is received and, based on the time differentials, determines the object's location. However, the GPS is impractical in many applications. The signal power levels from the satellites are low and the GPS receiver requires a clear, line-of-sight path to at least three satellites above a horizon of about 60 degrees for effective operation. Accordingly, inclement weather conditions, such as clouds, terrain features, such as hills and trees, and buildings restrict the ability of the GPS receiver to determine its position. Furthermore, the initial GPS signal detection process for a GPS receiver is relatively long (i.e., several minutes) for determining the receivers position. Such delays are unacceptable in many applications such as, for example, emergency response and vehicle tracking.
Differential GPS, or DGPS systems offer correction schemes to account for time synchronization drift. Such correction schemes include the transmission of correction signals over a two-way radio link or broadcast via FM radio station subcarriers. These systems have been found to be awkward and have met with limited success.
Additionally, GPS-based location systems have been attempted in which the received GPS signals are transmitted to a central data center for performing location calculations. Such systems have also met with limited success due, for example, to the limited reception of the satellite signals and the added expense and complexity of the electronics required for an inexpensive location mobile station or handset for detecting and receiving the GPS signals from the satellites.
The behavior of a mobile radio signal in the general environment is unique and complicated. Efforts to perform correlation between radio signals and distance between a base station and a mobile station are similarly complex. Repeated attempts to solve this problem in the past have been met with only marginal success. Factors include terrain undulations, fixed and variable clutter, atmospheric conditions, internal radio characteristics of cellular and PCS systems, such as frequencies, antenna configurations, modulation schemes, diversity methods, and the physical geometry of direct, refracted and reflected waves between the base stations and the mobile. Noise, such as man-made externally sources (e.g., auto ignitions) and radio system co-channel and adjacent channel interference also affect radio reception and related performance measurements, such as the analog carrier-to-interference ratio (C/I), or digital energy-per-bit/Noise density ratio (Eb/No) and are particular to various points in time and space domains.
Before discussing real world correlation between signals and distance, it is useful to review the theoretical premise, that of radio energy path loss across a pure isotropic vacuum propagation channel, and its dependencies within and among various communications channel types.
Over the last forty years various mathematical expressions have been developed to assist the radio mobile cell designer in establishing the proper balance between base station capital investment and the quality of the radio link, typically using radio energy field-strength, usually measured in microvolts/meter, or decibels.
One consequence from a location perspective is that the effective range of values for higher exponents is an increased at higher frequencies, thus providing improved granularity of ranging correlation.
Actual data collected in real-world environments uncovered huge variations with respect to the free space path loss equation, giving rise to the creation of many empirical formulas for radio signal coverage prediction. Clutter, either fixed or stationary in geometric relation to the propagation of the radio signals, causes a shadow effect of blocking that perturbs the free space loss effect. Perhaps the best known model set that characterizes the average path loss is Hata's, “Empirical Formula for Propagation Loss in Land Mobile Radio”, M. Hata, IEEE Transactions VT-29, pp. 317-325, August 1980, three pathloss models, based on Okumura's measurements in and around Tokyo, “Field Strength and its Variability in VHF and UHF Land Mobile Service”, Y. Okumura, et al, Review of the Electrical Communications laboratory, Vol 16, pp 825-873, September-October 1968.
Although the Hata model was found to be useful for generalized RF wave prediction in frequencies under 1 GHz in certain suburban and rural settings, as either the frequency and/or clutter increased, predictability decreased. In current practice, however, field technicians often have to make a guess for dense urban an suburban areas (applying whatever model seems best), then installing a base stations and begin taking manual measurements.
In 1991, U.S. Pat. No. 5,055,851 to Sheffer filed Nov. 29, 1989 taught that if three or more relationships have been established in a triangular space of three or more base stations (BSs) with a location database constructed having data related to possible mobile station (MS) locations, then arculation calculations may be performed, which use three distinct Por measurements to determine an X,Y, two dimensional location, which can then be projected onto an area map. The triangulation calculation is based on the fact that the approximate distance of the mobile station (MS) from any base station (BS) cell can be calculated based on the received signal strength. Sheffer acknowledges that terrain variations affect accuracy, although as noted above, Sheffer's disclosure does not account for a sufficient number of variables, such as fixed and variable location shadow fading, which are typical in dense urban areas with moving traffic.
Most field research before about 1988 has focused on characterizing (with the objective of RF coverage prediction) the RF propagation channel (i.e., electromagnetic radio waves) using a single-ray model, although standard fit errors in regressions proved dismal (e.g., 40-80 dB). Later, multi-ray models were proposed, and much later, certain behaviors were studied with radio and digital channels. In 1981, Vogler proposed that radio waves at higher frequencies could be modeled using optics principles. In 1988 Walfisch and Bertoni applied optical methods to develop a two-ray model, which when compared to certain highly specific, controlled field data, provided extremely good regression fit standard errors of within 1.2 dB.
In the Bertoni two ray model it was assumed that most cities would consist of a core of high-rise buildings surrounded by a much larger area having buildings of uniform height spread over regions comprising many square blocks, with street grids organizing buildings into rows that are nearly parallel. Rays penetrating buildings then emanating outside a building were neglected.
After a lengthy analysis it was concluded that path loss was a function of three factors: 1.) the path loss between antennas in free space; 2.) the reduction of rooftop wave fields due to settling; and 3.) the effect of diffraction of the rooftop fields down to ground level.
However, a substantial difficulty with the two-ray model in practice is that it requires a substantial amount of data regarding building dimensions, geometry, street widths, antenna gain characteristics for every possible ray path, etc. Additionally, it requires an inordinate amount of computational resources and such a model is not easily updated or maintained.
Unfortunately, in practice clutter geometry and building heights are random. Moreover, data of sufficient detail is extremely difficult to acquire, and regression standard fit errors are poor; i.e., in the general case, these errors were found to be 40-60 dB. Thus the two-ray model approach, although sometimes providing an improvement over single ray techniques, still did not predict RF signal characteristics in the general case to level of accuracy desired (<10 dB).
Work by Greenstein has since developed from the perspective of measurement-based regression models, as opposed to the previous approach of predicting-first, then performing measurement comparisons. Apparently yielding to the fact that low-power, low antenna (e.g., 12-25 feet above ground) height PCS microcell coverage was insufficient in urban buildings, Greenstein, et al, authored “Performance Evaluations for Urban Line-of-sight Microcells Using a Multi-ray Propagation Model”, in IEEE Globecom Proceedings, December 1991. This paper proposed the idea of formulating regressions based on field measurements using small PCS microcells in a lineal microcell geometry (i.e., geometries in which there is always a line-of-sight path between a subscriber's mobile and its current microsite). Additionally, Greenstein studied the communication channels variable Bit-Error-Rate (BER) in a spatial domain, which was a departure from previous research that limited field measurements to the RF propagation channel signal strength alone. However, Greenstein based his finding on two suspicious assumptions: 1) he assumed that distance correlation estimates were identical for uplink and downlink transmission paths; and 2) modulation techniques would be transparent in terms of improved distance correlation conclusions. Although some data held very correlation, other data and environments produced poor results. Accordingly, his results appear unreliable for use in general location context.
In 1993 Greenstein, et al, authored “A Measurement-Based Model for Predicting Coverage Areas of Urban Microcells”, in the IEEE Journal On Selected Areas in Communications, Vol. 11, No. 7, September 1993. Greenstein reported a generic measurement-based model of RF attenuation in terms of constant-value contours surrounding a given low-power, low antenna microcell environment in a dense, rectilinear neighborhood, such as New York City. However, these contours were for the cellular frequency band. In this case, LOS and non-LOS clutter were considered for a given microcell site. A result of this analysis was that RF propagation losses (or attenuation), when cell antenna heights were relatively low, provided attenuation contours resembling a spline plane curve depicted as an asteroid, aligned with major street grid patterns. Further, Greenstein found that convex diamond-shaped RF propagation loss contours were a common occurrence in field measurements in a rectilinear urban area. The special plane curve asteroid is represented by the formula:
x2/3+y2/3=r2/3. However, these results alone have not been sufficiently robust and general to accurately locate an mobile station, due to the variable nature of urban clutter spatial arrangements.
At Telesis Technology in 1994 Howard Xia, et al, authored “Microcellular Propagation Characteristics for Personal Communications in Urban and Suburban Environments”, in IEEE Transactions of Vehicular Technology, Vol. 43, No. 3, August 1994, which performed measurements specifically in the PCS 1.8 to 1.9 GHz frequency band. Xia found corresponding but more variable outcome results in San Francisco, Oakland (urban) and the Sunset and Mission Districts (suburban).
The physical radio propagation channel perturbs signal strength, frequency (causing rate changes, phase delay, signal to noise ratios (e.g., C/I for the analog case, or Eb/No, RF energy per bit, over average noise density ratio for the digital case) and Doppler-shift. Signal strength is usually characterized by:
Free Space Path Loss (Lp)
Slow fading loss or margin (Lslow)
Fast fading loss or margin (Lfast)
The cell designer increases the transmitted power PTX by the shadow fading margin Lslow which is usually chosen to be within the 1-2 percentile of the slow fading probability density function (PDF) to minimize the probability of unsatisfactorily low received power level PRX at the receiver. The PRX level must have enough signal to noise energy level (e.g., 10 dB) to overcome the receiver's internal noise level (e.g., −118 dBm in the case of cellular 0.9 GHz), for a minimum voice quality standard. Thus in this example PRX must never be below −108 dBm, in order to maintain the quality standard.
Additionally the short term fast signal fading due to multipath propagation is taken into account by deploying fast fading margin Lfast, which is typically also chosen to be a few percentiles of the fast fading distribution. The 1 to 2 percentiles compliment other network blockage guidelines. For example the cell base station traffic loading capacity and network transport facilities are usually designed for a 1-2 percentile blockage factor as well. However, in the worst-case scenario both fading margins are simultaneously exceeded, thus causing a fading margin overload.
In Roy Steele's, text, Mobile Radio Communications, IEEE Press, 1992, estimates for a GSM system operating in the 1.8 GHz band with a transmitter antenna height of 6.4 m and a mobile station receiver antenna height of 2 m, and assumptions regarding total path loss, transmitter power would be calculated as follows:
TABLE 1GSM Power Budget ExampleParameterdBm valueWill requireLslow14Lfast7LIpath110Min. RX pwr required−104TXpwr = 27 dBm
Steele's sample size in a specific urban London area of 80,000 LOS measurements and data reduction found a slow fading variance ofσ=7 dBassuming log-normal slow fading PDF and allowing for a 1.4% slow fading margin overload, thusLslow=2σ=14 dBThe fast fading margin was determined to be:Lfast=7 dB
In contrast, Xia's measurements in urban and suburban California at 1.8 GHz uncovered flat-land shadow fades on the order of 25-30 dB when the mobile station (MS) receiver was traveling from LOS to non-LOS geometries. In hilly terrain fades of +5 to −50 dB were experienced. Thus it is evident that attempts to correlate signal strength with mobile station ranging distance suggest that error ranges could not be expected to improve below 14 dB, with a high side of 25 to 50 dB. Based on 20 to 40 dB per decade, Corresponding error ranges for the distance variable would then be on the order of 900 feet to several thousand feet, depending upon the particular environmental topology and the transmitter and receiver geometries.
Although the acceptance of fuzzy logic has been generally more rapid in non-American countries, the principles of fuzzy logic can be applied in wireless location. Lotfi A. Zadeh's article, “Fuzzy Sets” published in 1965 in Information and Control, vol. 8, Pg 338-353, herein incorporated by reference, established the basic principles of fuzzy logic, among which a key theorem, the FAT theorem, suggests that a fuzzy system with a finite set of rules can uniformly approximate any continuous (or Borel-measureable) system. The system has a graph or curve in the space of all combinations of system inputs and outputs. Each fuzzy rule defines a patch in this space. The more uncertain the rule, the wider the patch. A finite number of small patches can always cover the curve. The fuzzy system averages patches that overlap. The Fat theorem was proven by Bart Kosko, in a paper entitled, “Fuzzy Systems as Universal Approximators”, in Proceedings of the First IEEE Conference on Fuzzy Systems, Pages 1153-1162, in San Diego, on March, 1992, herein incorporated by reference.
Fuzzy relations map elements of one universe, say “X”, to those of another universe, say “Y”, through the Cartesian product of the two universes. However, the “strength” of the relation between ordered pairs of the two universes is not measured with the characteristic function (in which an element is either definitely related to another element as indicated by a strength value of “1”, or is definitely not related to another element as indicated by a strength value of “0”, but rather with a membership function expressing various “degrees” of strength of the relation on the unit interval [0,1]. Hence, a fuzzy relation R is a mapping from the Cartesian space X×Y to the interval [0,1], where the strength of the mapping is expressed by the membership function of the relation for ordered pairs from the two universes or μR(x,y).
Just as for crisp relations, the properties of commutativity, associativity, distributivity, involution and idempotency all hold for fuzzy relations. Moreover, DeMorgan's laws hold for fuzzy relations just as they do for crisp (classical) relations, and the null relations O, and the complete relation, E, are analogous to the null set and the whole set in set-theoretic from, respectively. The properties that do not hold for fuzzy relations, as is the case for fuzzy sets in general, are the excluded middle laws. Since a fuzzy relation R is also a fuzzy set, there is overlap between a relation and its complement, hence.R∪R′≠ER∩R′≠O
As seen in the foregoing expression, the excluded middle laws for relation do not result in the null relation, O, or the complete relation, E. Because fuzzy relations in general are fuzzy sets, the Cartesian product can be defined as a relations between two or more fuzzy sets. Let A be a fuzzy set on universe X and B be a fuzzy set on universe Y; then the Cartesian product between fuzzy sets A and B will result in a fuzzy relation R, which is contained within the full Cartesian product space, orA×B=R⊂X×Y
where the fuzzy relation R has membership function:μR(x,y)=μA×B(x,y)=min(μA(x),μB(y))
Fuzzy composition can be defined just as it is for crisp (binary) relations. If R is a fuzzy relation on the Cartesian space X×Y, and S is a fuzzy relation on the Cartesian space Y×Z, and T is a fuzzy relation on the Cartesian space X×Z; then fuzzy max-min composition is defined in terms of the set-theoretic notation and membership function-theoretic notation in the following manner:μT(x,y)=(μR(x,y)μS(x,y))=max { min [μR(x,y),μS(y,z)]}
The fuzzy extension principle allows for transforms or mappings of fuzzy concepts in the form y=f(x). This principle, combined with a compositional rule of inference, allows for a crisp input to be mapped through a fuzzy transform using membership functions into a crisp output. Additionally, in mapping a variable x into a variable y, both x and y can be vector quantities.